ECE 6605 - Information Theory

Prof. Matthieu Bloch

Tuesday, November 14, 2023

Announcements

  • Project
    • Last assignment for the semester
    • Details discussed today
  • Exam options
    • Oral: list of problems forthcoming, scheduling options coming
    • Written: Thursday, December 14 11:20 am - 2:10 pm
  • Last time
    • Gaussian channels
    • Water filing power allocation
  • Today
    • Feedback
    • Soft-covering
  • Later this week
    • Secrecy and secret-key generation (??)

Projects

  • I. Land et al., Bounds on Information Combining, IEEE Transactions on Information Theory, (2005)
  • A. J. Goldsmith and P. P. Varaiya, Capacity of fading channels with channel side information, IEEE Transactions on Information Theory, (1997)
  • Sergio Verdu, \(α\)-Mutual Information, Proc of Information Theory and Applications Workshop, (2015)
  • M.H. Yassaee et al., Achievability Proof via Output Statistics of Random Binning, IEEE Transactions on Information Theory, (2014)
  • A. D. Wyner, The Wire-Tap Channel, Bell System Technical Journal, (1975)
  • Matthieu R. Bloch, Covert Communication over Noisy Channels: A Resolvability Perspective, IEEE Transactions on Information Theory, (2016)
  • Ken R. Duffy et al., Capacity-Achieving Guessing Random Additive Noise Decoding, IEEE Transactions on Information Theory, (2019)
  • S. Verdu, On channel capacity per unit cost, IEEE Transactions on Information Theory, (1990)

Projects

  • Andreas Winter et al., Commitment capacity of discrete memoryless channels, Proc. of 9th IMA international conference, (2003)
  • U.M. Maurer, Secret Key Agreement by Public Discussion from Common Information, IEEE Transactions on Information Theory, (1993)
  • Mihir Bellare et al., Semantic Security for the Wiretap Channel, Advances in Cryptology & CRYPTO 2012, (2012)
  • E. Arikan, Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels, IEEE Transactions on Information Theory, (2009)
  • Udo Wachsmann et al., Multilevel Codes: Theoretical Concepts and Practical Design Rules, IEEE Transactions on Information Theory, (1999)
  • Giuseppe Caire et al., Bit-interleaved Coded Modulation, IEEE Transactions on Information Theory, (1998)
  • V. Anantharam and S. Verdu, Bits through Queues, IEEE Transactions on Information Theory, (1996)

Writing a technical report

  • Why it matters
    • Engineers write code, solve equations, run simulations and build systems but… we also write a lot
    • Documenting our work allows us to retain and transfer knowledge
  • What are key features of a good technical report ?
    • Precision and conciseness are key
    • A technical report is not an essay; fancy grammar and syntax often come in the way of clarity
    • Diagrams, graphs, and equations are crucial to convey concepts and results
    • References to previous works provide the technical context and give proper credit
  • Structuring a report: there is a natural pattern to a technical report
    • Introduction: what is the big picture problem? What is the more specific aspect addressed here? what is the background knowledge? (this is where you put references)
    • Problem statement: what is the concrete technical problem formulation? (this is where you need to use the language of engineering, based on math and physics…)
    • Results: what have you achieved? (this is where you show results, analyze and criticize them)
    • References: list of bibliographic references

\(\LaTeX\)

  • \(\LaTeX\) is a tool to generate professional looking technical reports
    • Not everyone uses it, it is mostly used by physicists and mathematicians
    • There is a small learning curve but Word cannot even compete
    • It makes managing references much easier
  • A template is available at https://www.overleaf.com/read/nxypcxfdywbd
    • Download the template to start your report
  • BibTeX is the tool used to manage references

Technical writing

  • General recommendations
    • Proofread your report: grammar and syntax should be as polished as possible
    • Minimize the number of typos: the reader could judge the technical content of your report severely
    • Keep things simple: present tense is usually enough
    • Do not use informal language
    • Be precise: use equations, diagrams, etc.
  • Use of references
    • Do not quote or paraphrase references, but use references to support definitions, concepts, etc.
    • Provide context when describing results: do not assume the reader knows the paper and provide essential information
  • Equations and diagrams
    • Support your report with mathematics: just discussing a concept is not enough in engineering
    • Show that you understand the equations and how they relate to models, algorithms, etc.

Figures

  • General recommendations
    • If you use a figure from a source, reference it properly and give credit
    • Use vector graphics (PDF, SVG), which will display correctly regargless of resolution
    • Do not use screenshots: this makes a report look amateurish
    • Always comment and analyze figures
    • Always include a caption and reference the figure in the text

Frequently asked questions

  1. How long should the report be?
    • The report length should be commensurate with the effort you have put in the project
    • Deep down, you know whether your report reflects your work or not, this is how you take ownership and how I hold you accountable
  2. Can I use ChatGPT?
    • No. At this stage, ChatGPT is an impressive parrot, but there is a real risk that it will plagiarize someone's work without you realizing
  3. What kind and how many references should I use?
    • I want you to read research works. Wikipedia and web resources are convenient, but they are not considered authoritative resources
    • Read and cite research articles, textbooks, etc.
    • You have access to nearly everything through the GT library
  4. How will you evaluate my report?
    • Style: I will evaluate whether your report meets the standard of technical writing (structure, logic, quality of writing, etc.)
    • Substance: I will evaluate what you have done based on how you describe it

Channels with feedback

Soft covering

Image
Soft covering coding model
  • We assume for now that the message is uniformly distributed and that the input reference distirbution \(P_X\) is known and fixed.

A \((n,M_n)\) code \(\calC\) for soft covering over a discrete memoryless source \(P_{Z|X}\) consists of an encoding function \(f_n:\{1,\cdots,M_n\}\to\calX^n\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)
    2. The approximation of the output statistics \[ S^{(n)}\eqdef \mathbb{V}(P_Z^n,P_Z^{\otimes n}) \]

Channel resolvability

  • Define \[ C_{\textsf{r}}\eqdef \inf\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}D^{(n)}=0\right\} \]

For a discrete memoryless channel characterized by \(P_{Z|X}\) and an input \(P_X\), \(C_{\textsf{r}} = \mathbb{I}(X;Z)\)

  • Remarks
    • This result is called the channel coding theorem
    • Given a statistical characterization of a channel and an input distribution, we can randomize to lose structure
  • Proof of the result
    • We will use again an achievability and a converse

Achievability (random coding)

  • Consider a generic channel \((\calU,P_{V|U},\calV)\) with message set \(\{1,\cdots,M\}\)

  • For \(\gamma>0\), let

    \[\begin{align*} \calC_\gamma \eqdef \left\{(u,v)\in\calU\times\calV:\log\frac{P_{V|U}(v|u)}{P_V(v)}\leq\gamma\right\} \end{align*}\]

  • Encoder

    • For each \({m}\in\{1,\cdots,M\}\), \(f(m)\) is a codeword \(u\) drawn independently according to \(P_U\).

For any \(\gamma>0\),

\[\begin{align*} \E[C]{S(C)} \leq \P[P_UP_{V|U}]{(U,V)\notin \calC_\gamma} + \frac{1}{2}\sqrt{\frac{2^{\gamma}}{M}}. \end{align*}\]

Converse

Consider a sequence of codes \(\set{(f_n,g_n)}_{n\geq 1}\) such that \(\lim_{n\to\infty}S^{(n)}=0\) and \(\lim_{n\to\infty}\frac{\log M_n}{n}\geq R\). Then \[ R\geq \min_{P:P\circ P_{Z|X}=P_Z}\mathbb{I}(X;Z) \]